// run: time $exec < input
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 100005;
#define PB push_back

struct E {
	int v;
	int c;
};

vector<E> G[N];
int level[N];
void bfs(int end) {
	memset(level, 0, sizeof(level));
	queue<int> q;
	q.push(end);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < G[now].size(); ++i) {
			int ch = G[now][i].v;
			if (level[ch] == 0 && ch != end) {
				level[ch] = level[now] + 1;
				q.push(ch);
			}
		}
	}
}

int path[N];
int minn[N];
int used[N];
void dij(int n) {
	memset(path, 0x3f, sizeof(path));
	memset(minn, 0x3f, sizeof(minn));
	queue<E> q;
	q.push((E) { n, 0 });
	//used[0] = n;
	while (!q.empty()) {
		E now = q.front();
		q.pop();
		int now_level = level[now.v];
		if (now.c > path[now_level])
			continue;
		for (int i = 0; i < G[now.v].size(); ++i) {
			E ch = G[now.v][i];
			if (level[ch.v] == now_level - 1 && ch.c <= path[now_level - 1]) {
				path[now_level - 1] = ch.c;
				used[now_level - 1] = ch.v;
				//cout<<now_level - 1<<' '<<used[now_level - 1]<<endl;
				if (ch.c < minn[ch.v]) {
					minn[ch.v] = ch.c;
					q.push(ch);
				}
			}
		}
	}
}

void init(int n) {
	for (int i = 1; i <= n; ++i)
		G[i].clear();
}

long long const inf = 1 << 27;

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; ++i) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		++u, ++v;
		G[u].PB((E) { v, c });
		G[v].PB((E) { u, c });
	}
	bfs(1);
	dij(n);

	bool zero = true;
	for (int i = level[n] - 1; i >= 0; --i) {
		if (path[i]) zero = false;
		printf("%d", path[i]);
	}
	puts("");
	used[level[n]] = n;

	if (zero) {
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < (int)G[i].size(); j++) {
				int c = G[i][j].c;
				if (c) G[i][j].c = inf;
			}

		dij(n);
		int count = 0;
		for (int i = level[n] - 1; i >= 0; --i) count++;
		std::cout << count << '\n';
		for (int i = 0; i <= level[n]; ++i) {
			cout<<used[i] - 1<<' ';
		}
	} else {
		cout<<level[n] + 1<<endl;
		for (int i = 0; i <= level[n]; ++i) {
			cout<<used[i] - 1<<' ';
		}
		cout<<endl;
	}
}

